Năm 1511, một hạm đội Bồ Đào Nha đến dưới sự chỉ huy của Afonso de Albuquerque. Lực lượng của ông đã tấn công và đánh bại quân đội của Hồi quốc Malacca. Trong kế hoạch di chuyển nhanh chóng để củng cố thành quả của mình, Albuquerque đã cho xây dựng pháo đài xung quanh một ngọn đồi tự nhiên gần biển. Albuquerque tin rằng Malacca sẽ trở thành một cảng quan trọng nối Bồ Đào Nha với Tuyến đường Gia vị ở Trung Quốc. Vào thời điểm này, những người Bồ Đào Nha khác đang thiết lập các tiền đồn ở những nơi như Ma Cao, Trung Quốc và Goa, Ấn Độ để tạo ra một chuỗi các cảng thân thiện cho các tàu đi đến nhà Minh ở Trung Quốc.và trở về nhà ở Bồ Đào Nha.

Các pháo đài một lần bao gồm dài thành lũy và bốn tháp lớn. Một trong những tòa tháp cao nhất pháo đài cao 60m, được gọi là A Famosa ('nổi tiếng'), đó là công trình cao nhất trong khu vực từ năm 1512 cho đến khi nó bị phá hủy bởi người Hà Lan trong năm 1641,[1] khác các khu vực của pháo đài bao gồm một phòng chứa đạn dược, nơi ở của thuyền trưởng và khu dành cho sĩ quan. Cũng có những ngôi nhà phố bên trong các bức tường của pháo đài. Dân số Malacca mở rộng đã làm pháp đài ban đầu bị quá tải và các phần mở rộng được xây dựng thêm vào khoảng năm 1586.

Pháo đài đổi chủ vào năm 1641 khi người Hà Lan đánh đuổi người Bồ Đào Nha khỏi Malacca.[2] Người Hà Lan đã cải tạo cổng của pháo đài vào năm 1670, điều này giải thích cho việc logo "ANNO 1670" được khắc trên vòm cổng. Phía trên vòm có một bức phù điêu logo của Công ty Đông Ấn Hà Lan.

Pháo đài lại đổi chủ vào cuối thế kỷ 18 khi người Hà Lan giao nó cho người Anh để ngăn nó rơi vào tay nước Pháp dưới sự bành trướng của Napoléon. Người Anh đã cảnh giác với việc duy trì pháo đài và ra lệnh phá hủy nó vào năm 1806. Pháo đài gần như đã bị phá hủy hoàn toàn nhưng nhờ sự can thiệp kịp thời của Sir Stamford Raffles, người sáng lập ra Singapore hiện đại, người đã được gửi đi nghỉ ốm từ Penang đến Malacca vào năm 1807. Đó là Đại úy William Farquhar, được giao nhiệm vụ phá hủy pháo đài và thị trấn, người đã quyết định cứu hai trong số các cổng vào pháo đài,bao gồm cổng Santiago, cũng như Stadthuys, nhà thờ và nhà tù.